package com.yoshino.leetcode.improve40.fifth;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] a = new int[26], b = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            a[s1.charAt(i) - 'a']++;
            b[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(a, b)) {
            return true;
        }
        int left = 0, right = s1.length();
        while (right < s2.length()) {
            b[s2.charAt(left) - 'a']--;
            b[s2.charAt(right) - 'a']++;
            if (Arrays.equals(a, b)) {
                return true;
            }
            right++;
            left++;
        }
        return false;
    }

    public List<Integer> findAnagrams(String s, String p) {
        int pl = p.length();
        if (s.length() < pl) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        int[] count = new int[26];
        for (int i = 0; i < pl; i++) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }

        int differ = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                differ++;
            }
        }

        if (differ == 0) {
            res.add(0);
        }

        for (int i = 0; i < s.length() - pl; i++) {
            if (count[s.charAt(i) - 'a'] == 1) {
                differ--;
            } else if (count[s.charAt(i) - 'a'] == 0) {
                differ++;
            }
            count[s.charAt(i) - 'a']--;
            if (count[s.charAt(i + pl) - 'a'] == -1) {
                differ--;
            } else if (count[s.charAt(i + pl) - 'a'] == 0) {
                differ++;
            }
            count[s.charAt(i + pl) - 'a']++;
            if (differ == 0) {
                res.add(i + 1);
            }
        }
        return res;
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int left = 0, right = 0, max = 0;
        int[] cur = new int[128];
        while (right < s.length()) {
            cur[s.charAt(right)]++;
            if (cur[s.charAt(right)] == 1) {
                max = Math.max(max, right - left + 1);
            } else {
                while (cur[s.charAt(right)] != 1) {
                    cur[s.charAt(left)]--;
                    left++;
                }
            }
            right++;
        }
        return max;
    }
}